package my.Imitation.writing;
/**
 * Created with IntelliJ IDEA.
 *
 * @Author: Tom
 * @Date: 2022/01/21/21:20
 * @Description:
 */

import java.util.NoSuchElementException;

/**
 *@ClassName LinkedList
 *@Description
 *@Author 王琛
 *@Date 2022/1/21 21:20
 @Version 1.0
 */
public class MyLinkedList<E> {

    private static class Node<E>{
         E item;
         Node<E> pre;
         Node<E> next;
         Node(Node<E> pre, E item,  Node<E> next) {
           this.item = item;
           this.pre = pre;
           this.next = next;
         }
    }

    Node<E> first;
    Node<E> last;
    int size = 0;

    public MyLinkedList() {
    }

    public boolean add(E e){
        linkLast(e);
        return true;
    }

    public boolean add(E e,int index) {
        checkIndex(index);
        if (index == size) {
            linkLast(e);
        }else{
            linkBefore(e,findByIndex(index));
        }
        return true;
    }
    public boolean addFirst(E e){
        linkFirst(e);
        return true;
    }
    public boolean addLast(E e) {
        linkLast(e);
        return true;
    }

    public E get(int index){
        checkIndex(index);
        return findByIndex(index).item;
    }
    public E getFirst(){
        Node<E> f = first;
        if (f == null) {
            throw new NoSuchElementException();
        }
        return f.item;
    }

    public E getLast(){
        Node<E> l = last;
        if (l == null) {
            throw new NoSuchElementException();
        }
        return l.item;
    }

    public E set(E e, int index){
        checkIndex(index);
        Node<E> oldNode = findByIndex(index);
        E old = oldNode.item;
        oldNode.item = e;
        return old;
    }


    public void checkIndex(int index){
        if (index <= 0 || index > size) {
          throw new IndexOutOfBoundsException("");
        }
    }
    public void linkLast(E e){
        Node<E> l = last;
        Node<E> newNode = new Node<E>(l,e,null);
        last = newNode;
        if (l == null) {
            first = newNode;
        }else{
        l.next = newNode;
        }
        size ++;
    }

    public void linkFirst(E e){
        Node<E> f = first;
        Node<E> newNode = new Node<E>(null,e,f);
        first = newNode;
        if (f == null) {
            last = newNode;
        }else{
            f.pre = newNode;
        }
        size ++;
    }


    public void linkBefore(E e, Node<E> node){
        Node<E> pre = node.pre;
        Node<E> newNode = new Node<E>(pre,e,node);
        if(pre == null){
            first = newNode;
        }else{
            pre.next = newNode;
        }
        size++;
    }

    public boolean remove(Object o) {
        Node<E> f = first;
        if (o == null) {
            while (f != null) {
                if (f.item == null) {
                    unlink(f);
                    return true;
                }
                f = f.next;
            }
        } else {
            while (f != null) {
                if (f.item == o) {
                    unlink(f);
                    return true;
                }
                f = f.next;
            }
        }
        return false;
    }

    public E removeLast(){
        Node<E> l = last;
        if (last == null) {
            throw new NoSuchElementException();
        }
        E item = l.item;
        Node<E> prev = l.pre;
        last = prev;
        l.pre = null;
        if (prev == null) {
            first = null;
        }else {
            prev.next = null;
        }
        size--;
        return item;
    }

    public E removeFirst() {
        Node<E> f = first;
        if (first == null) {
            throw new NoSuchElementException();
        }
        E item = f.item;
        Node<E> next = f.next;
        first = next;
        f.next = null;
        if (next == null) {
           last = null;
        }else{
            next.pre = null;
        }
        size --;
        return item;
    }

    public E unlink(Node<E> e){
        final E item = e.item;
        final Node<E> prev = e.pre;
        final Node<E> next = e.next;
        if (prev == null) {
            first = next;
            next.pre = null;
        }else{
            prev.next = next;
            e.pre = null;
        }
        if (next == null){
            last = prev;
        }else {
            next.pre = prev;
            e.next = null;
        }
        e.item = null;
        size--;
        return item;
    }

    public Node<E> findByIndex(int index){
        int mid = size >> 1;
        Node<E> f = first;
        Node<E> l = last;
        if (index == size){
            return l;
        }
        if(index < mid){
            for (int i = 0; i < index; i++) {
                f = f.next;
            }
            return f;
        }else{
            for (int j = size; size > index; j --){
                l = l.pre;
            }
            return l;
        }
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }
}
